// OpentTxl-C Version 11 grammar analyzer
// J.R. Cordy, Jan 2023

// Copyright 2023, James R. Cordy and others

// Permission is hereby granted, free of charge, to any person obtaining a copy of this software 
// and associated documentation files (the “Software”), to deal in the Software without restriction, 
// including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, 
// and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, 
// subject to the following conditions:

// The above copyright notice and this permission notice shall be included in all copies 
// or substantial portions of the Software.

// THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, 
// INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE 
// AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, 
// DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

// The TXL grammar analyzer
// Grammar analysis tools - used by the grammar compiler when the -analyze command line option is specified

// Modification Log

// v11.0 Initial revision, adapted from OpenTxl 11.0

#include "support.h"

#include "limits.h"
#include "tokens.h"
#include "errors.h"
#include "trees.h"
#include "shared.h"
#include "idents.h"
#include "symbols.h"

#include "analyze.h"

static bool analyzeGrammar_boundedDerivesEmpty (const treePT defineTP, const int depth)
{
    // derives_empty (X)   = true if X is of kind and name empty,
    //                = true if X is of type generatelist or generaterepeat,
    //                = true if X is of type choose, and derives_empty (one kid of X)
    //                = true if X is of type order, and derives_empty (all kids of X)

    if (depth > symbol_nSymbols) {
        // give up, don't know, probably no
        return (false);
    }

    // Is this the one we're looking for?
    if (tree_trees[defineTP].kind == treeKind_empty) {
        return (true);
    }

    // If not, is it worth looking deeper?
    if (tree_trees[defineTP].kind >= treeKind_empty) {
        return (false);
    }

    // Cached result - do we already know?
    if (tree_trees[defineTP].derivesEmpty == derivesT_yes) {
        return (true);
    } else {
        if (tree_trees[defineTP].derivesEmpty == derivesT_no) {
            return (false);
        }
    }

    // Now look deeper
    if ((tree_trees[defineTP].kind == treeKind_generaterepeat) 
            || (tree_trees[defineTP].kind == treeKind_generatelist) 
            || (tree_trees[defineTP].kind == treeKind_lookahead)) {
        tree_setDerivesEmpty (defineTP, derivesT_yes);
        return (true);
    } else if (tree_trees[defineTP].kind == treeKind_leftchoose) {
        if (analyzeGrammar_boundedDerivesEmpty (tree_kid1TP (defineTP), depth + 1)) {
            tree_setDerivesEmpty (defineTP, derivesT_yes);
            return (true);
        } else {
            tree_setDerivesEmpty (defineTP, derivesT_no);
            return (false);
        }
    } else if (tree_trees[defineTP].kind == treeKind_choose) {
        for (int i = 1; i <= tree_trees[defineTP].count; i++) {
            if (analyzeGrammar_boundedDerivesEmpty (tree_kidTP (i, defineTP), depth + 1)) {
                tree_setDerivesEmpty (defineTP, derivesT_yes);
                return (true);
            }
        }
        tree_setDerivesEmpty (defineTP, derivesT_no);
        return (false);
    } else if (tree_trees[defineTP].kind == treeKind_order) {
        for (int i = 1; i <= tree_trees[defineTP].count; i++) {
            if (!analyzeGrammar_boundedDerivesEmpty (tree_kidTP (i, defineTP), depth + 1)) {
                tree_setDerivesEmpty (defineTP, derivesT_no);
                return (false);
            }
        }
        tree_setDerivesEmpty (defineTP, derivesT_yes);
        return (true);
    } else if ((tree_trees[defineTP].kind == treeKind_repeat) || (tree_trees[defineTP].kind == treeKind_list) 
                || (tree_trees[defineTP].kind == treeKind_push) || (tree_trees[defineTP].kind == treeKind_pop)) {
        if (analyzeGrammar_boundedDerivesEmpty (tree_kid1TP (defineTP), depth + 1)) {
            tree_setDerivesEmpty (defineTP, derivesT_yes);
            return (true);
        } else {
            tree_setDerivesEmpty (defineTP, derivesT_no);
            return (false);
        }
    } else {
        tree_setDerivesEmpty (defineTP, derivesT_no);
        return (false);
    }
}

// Bounded derivation analysis
static array (treePT, analyzeGrammar_derivesList);  // [maxSymbols]
static int analyzeGrammar_derivesLength;
static bool analyzeGrammar_derivesThroughRepeat;

static bool analyzeGrammar_boundedDerives (const treePT defineTP, const treePT targetTP, const bool throughRepeat, const int depth)
{
    // derives (X,Y)   = true if X is of type Y,
    //            = true if X is of type choose, and derives (one kid of X,Y)
    //            = true if X is of type order, and derives (one kid of X,Y)
    //                                          and derives (other kids of X,empty)

    if (depth > symbol_nSymbols) {
        // give up, don't know, probably no
        return (false);
    }

    // Is this the one we're looking for?
    if ((tree_trees[defineTP].kind == tree_trees[targetTP].kind) 
            && ((tree_trees[defineTP].name == tree_trees[targetTP].name) || (tree_trees[targetTP].kind == treeKind_empty))) {
        analyzeGrammar_derivesThroughRepeat = throughRepeat;
        return (true);
    }

    // If no, is it worth looking deeper?
    if (tree_trees[defineTP].kind >= firstLeafKind) {
        return ((tree_trees[defineTP].kind == treeKind_token) && (tree_trees[targetTP].kind >= firstLiteralKind));
    }

    // Keep track of where we've already looked
    if (depth == 0) {
        analyzeGrammar_derivesLength = 0;
    }

    for (int i = 1; i <= analyzeGrammar_derivesLength; i++) {
        if ((tree_trees[analyzeGrammar_derivesList[i]].name == tree_trees[defineTP].name) 
                && (tree_trees[analyzeGrammar_derivesList[i]].kind == tree_trees[defineTP].kind)) {
            // been there, done that
            return (false);  // true maybe?
        }
    }

    assert (analyzeGrammar_derivesLength < symbol_nSymbols);
    analyzeGrammar_derivesLength += 1;
    analyzeGrammar_derivesList[analyzeGrammar_derivesLength] = defineTP;

    // Now look deeper
    if ((tree_trees[defineTP].kind == treeKind_generaterepeat) || (tree_trees[defineTP].kind == treeKind_generatelist)) {
        return ((tree_trees[targetTP].kind == treeKind_empty) 
            || analyzeGrammar_boundedDerives (tree_kid1TP (defineTP), targetTP, true, depth + 1));
    } else if (tree_trees[defineTP].kind == treeKind_lookahead) {
        return (tree_trees[targetTP].kind == treeKind_empty);
    } else if (tree_trees[defineTP].kind == treeKind_leftchoose) {
        return (analyzeGrammar_boundedDerives (tree_kid1TP (defineTP), targetTP, throughRepeat, 
                    depth + 1) 
            || (analyzeGrammar_boundedDerives (tree_kid1TP (defineTP), emptyTP, throughRepeat, 
                    depth + 1) 
                && analyzeGrammar_boundedDerives (tree_kid2TP (tree_kid2TP (defineTP)), targetTP, 
                    throughRepeat, depth + 1)));
    } else if (tree_trees[defineTP].kind == treeKind_choose) {
        for (int i = 1; i <= tree_trees[defineTP].count; i++) {
            if (analyzeGrammar_boundedDerives (tree_kidTP (i, defineTP), targetTP, throughRepeat, depth + 1)) {
                return (true);
            }
        }
        return (false);
    } else if (tree_trees[defineTP].kind == treeKind_order) {
        for (int i = 1; i <= tree_trees[defineTP].count; i++) {
            if (analyzeGrammar_boundedDerives (tree_kidTP (i, defineTP), targetTP, throughRepeat, depth + 1)) {
                if (i < tree_trees[defineTP].count) {
                    for (int j = i + 1; j <= tree_trees[defineTP].count; j++) {
                        if (!analyzeGrammar_boundedDerivesEmpty (tree_kidTP (j, defineTP), depth + 1)) 
                            break;
                        if (j == tree_trees[defineTP].count) {
                            analyzeGrammar_derivesThroughRepeat = throughRepeat;
                            return (true);
                        }
                    }
                } else {
                    return (true);
                }
            }
            if (!analyzeGrammar_boundedDerivesEmpty (tree_kidTP (i, defineTP), depth + 1)) 
                break;
        }
        return (false);
    } else if ((tree_trees[defineTP].kind == treeKind_repeat) || (tree_trees[defineTP].kind == treeKind_list)) {
        return (analyzeGrammar_boundedDerives (tree_kid1TP (defineTP), targetTP, true, depth + 1) 
            || (analyzeGrammar_boundedDerives (tree_kid1TP (defineTP), emptyTP, false, depth + 1) 
                && analyzeGrammar_boundedDerives (tree_kid2TP (defineTP), targetTP, true, depth + 1)));
    } else if ((tree_trees[defineTP].kind == treeKind_push) || (tree_trees[defineTP].kind == treeKind_pop)) {
        return (analyzeGrammar_boundedDerives (tree_kid1TP (defineTP), targetTP, true, depth + 1));
    } else {
        return (false);
    }
}

static bool analyzeGrammar_derives (const treePT defineTP, const treePT targetTP)
{
    if (tree_trees[targetTP].kind == treeKind_empty) {
        return (analyzeGrammar_boundedDerivesEmpty (defineTP, 0));
    } else {
        return (analyzeGrammar_boundedDerives (defineTP, targetTP, false, 0));
    }
}

static array (treePT, analyzeGrammar_derivesLeadingList);
static int analyzeGrammar_derivesLeadingLength;  // = 0

static bool analyzeGrammar_boundedDerivesLeading (const treePT defineTP, const treePT targetTP, const int depth)
{
    // derivesLeading (X,Y)   = true if X is of type Y,
    //            = true if X is of type choose, and derivesLeading (one kid of X,Y)
    //            = true if X is of type order, and derivesLeading (one kid of X,Y)
    //                                          and derivesLeading (previous kids of X,empty)
        
    if (depth > symbol_nSymbols) {
        // give up, don't know, probably no
        return (false);
    }

    // Is this the one we're looking for?
    if ((tree_trees[defineTP].kind == tree_trees[targetTP].kind) 
            && ((tree_trees[defineTP].name == tree_trees[targetTP].name) 
                || (tree_trees[targetTP].kind == treeKind_empty))) {
        return (true);
    }

    // If not, is it worth looking deeper?
    if (tree_trees[defineTP].kind >= firstLeafKind) {
        return ((tree_trees[defineTP].kind == treeKind_token) && (tree_trees[targetTP].kind >= treeKind_literal));
    }

    // Keep track of where we've already looked
    if (depth == 0) {
        analyzeGrammar_derivesLeadingLength = 0;
    }

    for (int i = 1; i <= analyzeGrammar_derivesLeadingLength; i++) {
        if ((tree_trees[analyzeGrammar_derivesLeadingList[i]].name == tree_trees[defineTP].name) 
                && (tree_trees[analyzeGrammar_derivesLeadingList[i]].kind == tree_trees[defineTP].kind)) {
            // been there, done that
            return (false);
        }
    }

    assert (analyzeGrammar_derivesLeadingLength < symbol_nSymbols);
    analyzeGrammar_derivesLeadingLength += 1;
    analyzeGrammar_derivesLeadingList[analyzeGrammar_derivesLeadingLength] = defineTP;

    // Now look deeper
    if ((tree_trees[defineTP].kind) == treeKind_generaterepeat || (tree_trees[defineTP].kind == treeKind_generatelist)) {
        return ((tree_trees[targetTP].kind == treeKind_empty) 
            || analyzeGrammar_boundedDerivesLeading (tree_kid1TP (defineTP), targetTP, depth + 1));
    } else if (tree_trees[defineTP].kind == treeKind_lookahead) {
        return (tree_trees[targetTP].kind == treeKind_empty);
    } else if (tree_trees[defineTP].kind == treeKind_leftchoose) {
        return (analyzeGrammar_boundedDerivesLeading (tree_kid1TP (defineTP), targetTP, depth + 1) 
            || (analyzeGrammar_derives (tree_kid1TP (defineTP), emptyTP) 
                && analyzeGrammar_boundedDerivesLeading (tree_kid2TP (tree_kid2TP (defineTP)), 
                    targetTP, depth + 1)));
    } else if (tree_trees[defineTP].kind == treeKind_choose) {
        for (int i = 1; i <= tree_trees[defineTP].count; i++) {
            if (analyzeGrammar_boundedDerivesLeading (tree_kidTP (i, defineTP), targetTP, depth + 1)) {
                return (true);
            }
        }
        return (false);
    } else if (tree_trees[defineTP].kind == treeKind_order) {
        for (int i = 1; i <= tree_trees[defineTP].count; i++) {
            if (analyzeGrammar_boundedDerivesLeading (tree_kidTP (i, defineTP), targetTP, depth + 1)) {
                return (true);
            }
            if (!analyzeGrammar_derives (tree_kidTP (i, defineTP), emptyTP)) 
                break;
        }
        return (false);
    } else if ((tree_trees[defineTP].kind == treeKind_repeat) || (tree_trees[defineTP].kind == treeKind_list)) {
        assert (tree_trees[defineTP].count == 2);
        return (analyzeGrammar_boundedDerivesLeading (tree_kid1TP (defineTP), targetTP, depth + 1) 
            || (analyzeGrammar_derives (tree_kid1TP (defineTP), emptyTP) 
                && analyzeGrammar_boundedDerivesLeading (tree_kid2TP (defineTP), targetTP, depth + 1)));
    } else if ((tree_trees[defineTP].kind == treeKind_push) || (tree_trees[defineTP].kind == treeKind_pop)) {
        return (analyzeGrammar_boundedDerivesLeading (tree_kid1TP (defineTP), targetTP, depth + 1));
    } else {
        return (false);
    }
}

static bool analyzeGrammar_derivesLeading (const treePT defineTP, const treePT targetTP)
{
    return (analyzeGrammar_boundedDerivesLeading (defineTP, targetTP, 0));
}

static bool analyzeGrammar_boundedContains (const treePT defineTP, const treePT targetTP, const int depth)
{
    // contains (X,Y)  = true if X is of type Y,
    //                 = true if X is of type choose or order, and contains (one kid of X,Y)

    if (depth > symbol_nSymbols) {
        // give up, don't know, probably no
        return (false);
    }

    // Is this the one we're looking for?
    if ((tree_trees[defineTP].kind == tree_trees[targetTP].kind) 
            && ((tree_trees[defineTP].name == tree_trees[targetTP].name) || (tree_trees[targetTP].kind == treeKind_empty))) {
        return (true);
    }

    // If not, is it worth looking deeper?
    if (tree_trees[defineTP].kind >= firstLeafKind) {
        return ((tree_trees[defineTP].kind == treeKind_token) && (tree_trees[targetTP].kind >= firstLiteralKind));
    }

    // Keep track of where we've already looked, using same list as derives()
    if (depth == 0) {
        analyzeGrammar_derivesLength = 0;
    }

    for (int i = 1; i <= analyzeGrammar_derivesLength; i++) {
        if ((tree_trees[analyzeGrammar_derivesList[i]].name == tree_trees[defineTP].name) 
                && (tree_trees[analyzeGrammar_derivesList[i]].kind == tree_trees[defineTP].kind)) {
            // been there, done that
            return (false);
        }
    }

    assert (analyzeGrammar_derivesLength < symbol_nSymbols);
    analyzeGrammar_derivesLength += 1;
    analyzeGrammar_derivesList[analyzeGrammar_derivesLength] = defineTP;

    // Now look deeper
    if ((tree_trees[defineTP].kind == treeKind_generaterepeat) || (tree_trees[defineTP].kind == treeKind_generatelist)) {
        return (analyzeGrammar_boundedContains (tree_kid1TP (defineTP), targetTP, depth + 1));
    } else if ((tree_trees[defineTP].kind == treeKind_choose) || (tree_trees[defineTP].kind == treeKind_order) 
                || (tree_trees[defineTP].kind == treeKind_repeat) || (tree_trees[defineTP].kind == treeKind_list) 
                || (tree_trees[defineTP].kind == treeKind_leftchoose)) {
        for (int i = 1; i <= tree_trees[defineTP].count; i++) {
            if (analyzeGrammar_boundedContains (tree_kidTP (i, defineTP), targetTP, depth + 1)) {
                return (true);
            }
        }
        return (false);
    } else {
        return (false);
    }
}

static bool analyzeGrammar_contains (const treePT defineTP, const treePT targetTP)
{
    return (analyzeGrammar_boundedContains (defineTP, targetTP, 0));
}

// Grammar sorting
static int analyzeGrammar_nSortedSymbols;
static array (treePT, analyzeGrammar_sortedSymbols);
static array (int, analyzeGrammar_sortedSymbolDepth);

static void analyzeGrammar_sortGrammarSymbolsTraversal (const treePT grammarTP, const int depth)
{
    if ((grammarTP == nilTree) 
            || (tree_trees[grammarTP].kind == treeKind_literal) 
            || (tree_trees[grammarTP].kind == treeKind_empty)) {
        return;
    }

    // if we've already visited it, don't do so again
    for (int g = analyzeGrammar_nSortedSymbols; g >= 1; g--) {
        if (grammarTP == (analyzeGrammar_sortedSymbols[g])) {
            return;
        }
    }

    analyzeGrammar_nSortedSymbols += 1;
    analyzeGrammar_sortedSymbols[analyzeGrammar_nSortedSymbols] = grammarTP;
    analyzeGrammar_sortedSymbolDepth[analyzeGrammar_nSortedSymbols] = depth;

    switch (tree_trees[grammarTP].kind) {
        case treeKind_order: case treeKind_repeat: case treeKind_list: case treeKind_choose: case treeKind_leftchoose: 
        case treeKind_generaterepeat: case treeKind_generatelist: case treeKind_lookahead: case treeKind_push: case treeKind_pop:
            {
                const kidPT kidBase = tree_trees[grammarTP].kidsKP - 1;
                for (int k = 1; k <= tree_trees[grammarTP].count; k++) {
                    analyzeGrammar_sortGrammarSymbolsTraversal (tree_kids[kidBase + k], depth + 1);
                }
            }
            break;
        default :
            break;
    }
}

static void analyzeGrammar_sortGrammarSymbols (const treePT grammarTP)
{
    analyzeGrammar_nSortedSymbols = 0;
    analyzeGrammar_sortGrammarSymbolsTraversal (grammarTP, 1);
    for (int i = 1; i <= analyzeGrammar_nSortedSymbols - 1; i++) {
        int j = i;
        for (int k = i + 1; k <= analyzeGrammar_nSortedSymbols; k++) {
            if (analyzeGrammar_sortedSymbolDepth[k] 
                    < analyzeGrammar_sortedSymbolDepth[j]) {
                j = k;
            }
        }
        if (j != i) {
            const int ssti = analyzeGrammar_sortedSymbols[i];
            const int sstd = analyzeGrammar_sortedSymbolDepth[i];
            analyzeGrammar_sortedSymbols[i] = analyzeGrammar_sortedSymbols[j];
            analyzeGrammar_sortedSymbolDepth[i] = analyzeGrammar_sortedSymbolDepth[j];
            analyzeGrammar_sortedSymbols[j] = ssti;
            analyzeGrammar_sortedSymbolDepth[j] = sstd;
        }
    }
}

void analyzeGrammar_checkAdjacentCombinatorialAmbiguity (const treePT defineTP, const treePT grammarTP)
{
    // We have an adjacent combinatorial ambiguity if an order node
    // has two effectively adjacent kids that can derive a common symbol through a repeat or list
    if (tree_trees[defineTP].kind == treeKind_order) {

        analyzeGrammar_sortGrammarSymbols (defineTP);

        const kidPT kidBase = tree_trees[defineTP].kidsKP - 1;

        for (int i = 2; i <= analyzeGrammar_nSortedSymbols; i++) {
            const treePT symbolTP = analyzeGrammar_sortedSymbols[i];

            if ((tree_trees[symbolTP].kind != treeKind_literal) && (tree_trees[symbolTP].kind != treeKind_empty)) {
                for (int k = 1; k <= tree_trees[defineTP].count - 1; k++) {
                    if (analyzeGrammar_derives (tree_kids[kidBase + k], symbolTP) 
                            && analyzeGrammar_derivesThroughRepeat) {
                        for (int k2 = k + 1; k2 <= tree_trees[defineTP].count; k2++) {
                            if (analyzeGrammar_derives (tree_kids[kidBase + k2], symbolTP) 
                                    && analyzeGrammar_derivesThroughRepeat) {
                                string defineexttype;
                                externalType (*ident_idents[tree_trees[defineTP].name], defineexttype);
                                string symbolexttype;
                                externalType (*ident_idents[tree_trees[symbolTP].name], symbolexttype);
                                string context, message;
                                stringprintf (context, "define '%s'", defineexttype);
                                stringprintf (message, "[%s] is combinatorially ambiguous when parsing sequences of [%s]",
                                    defineexttype, symbolexttype); 
                                error (context, message, WARNING, 215);
                                fprintf (stderr, "  since [%s] -> ", defineexttype);
                                if (k > 1) {
                                    fprintf (stderr, "... ");
                                }
                                for (int j = k; j <= k2; j++) {
                                    string kidjexttype;
                                    externalType (*ident_idents[tree_trees[tree_kids[kidBase + j]].name], kidjexttype);
                                    
                                    fprintf (stderr, "[%s] ", kidjexttype);
                                }
                                if (k2 < tree_trees[defineTP].count) {
                                    fprintf (stderr, " ...\n");
                                } else {
                                    fprintf (stderr, "\n");
                                }
                                string kidkexttype;
                                externalType (*ident_idents[tree_trees[tree_kids[kidBase + k]].name], kidkexttype);
                                fprintf (stderr, "   and  [%s] ->* ", kidkexttype);
                                if ((tree_trees[tree_kids[kidBase + k]].kind != treeKind_generaterepeat) 
                                        && (tree_trees[tree_kids[kidBase + k]].kind != treeKind_repeat) 
                                        && (tree_trees[tree_kids[kidBase + k]].kind != treeKind_generatelist) 
                                        && (tree_trees[tree_kids[kidBase + k]].kind != treeKind_list)) {
                                    for (int j = 2; j <= analyzeGrammar_nSortedSymbols; j++) {
                                        treePT sjTP = analyzeGrammar_sortedSymbols[j];
                                        if (((tree_trees[sjTP].kind == treeKind_generaterepeat) 
                                                        || (tree_trees[sjTP].kind == treeKind_repeat) 
                                                        || (tree_trees[sjTP].kind == treeKind_generatelist) 
                                                        || (tree_trees[sjTP].kind == treeKind_list)) 
                                                    && analyzeGrammar_derives (sjTP, symbolTP) 
                                                    && analyzeGrammar_derives (tree_kids[kidBase + k], sjTP)) {
                                            string sjTPexttype;
                                            externalType (*ident_idents[tree_trees[sjTP].name], sjTPexttype);
                                            fprintf (stderr, "[%s] ->* ", sjTPexttype);
                                            break;
                                        }
                                        assert (j != analyzeGrammar_nSortedSymbols);
                                    }
                                }
                                fprintf (stderr, "[%s]\n", symbolexttype);
                                for (int j = k + 1; j <= k2 - 1; j++) {
                                    string kidjexttype;
                                    externalType (*ident_idents[tree_trees[tree_kids[kidBase + j]].name], kidjexttype);
                                    fprintf (stderr, "   and  [%s] ->", kidjexttype);
                                    if (tree_trees[tree_kids[kidBase + j]].kind != treeKind_empty) {
                                        fprintf (stderr, "*");
                                    }
                                    fprintf (stderr, " [empty]\n");
                                }
                                string kidk2exttype;
                                externalType (*ident_idents[tree_trees[tree_kids[kidBase + k2]].name], kidk2exttype);
                                fprintf (stderr, "   and  [%s] ->* ", kidk2exttype);
                                if ((tree_trees[tree_kids[kidBase + k2]].kind != treeKind_generaterepeat) 
                                        && (tree_trees[tree_kids[kidBase + k2]].kind != treeKind_repeat) 
                                        && (tree_trees[tree_kids[kidBase + k2]].kind != treeKind_generatelist) 
                                        && (tree_trees[tree_kids[kidBase + k2]].kind != treeKind_list)) {
                                    for (int j = 2; j <= analyzeGrammar_nSortedSymbols; j++) {
                                        treePT sjTP = analyzeGrammar_sortedSymbols[j];
                                        if (((tree_trees[sjTP].kind == treeKind_generaterepeat) 
                                                    || (tree_trees[sjTP].kind == treeKind_repeat) 
                                                    || (tree_trees[sjTP].kind == treeKind_generatelist) 
                                                    || (tree_trees[sjTP].kind == treeKind_list)) 
                                                && analyzeGrammar_derives (sjTP, symbolTP) 
                                                && analyzeGrammar_derives (tree_kids[kidBase + k2], sjTP)) {
                                            string sjTPexttype;
                                            externalType (*ident_idents[tree_trees[sjTP].name], sjTPexttype);
                                            fprintf (stderr, "[%s] ->* ", sjTPexttype);
                                            break;
                                        }
                                        assert (j != analyzeGrammar_nSortedSymbols);
                                    }
                                }
                                fprintf (stderr, "[%s]\n", symbolexttype);
                                fprintf (stderr, "  (parsing and/or syntax error detection may be slow)\n");
                                // Show only the first one we hit - in a sorted subgrammar,
                                // this is the highest level symbol with the problem
                                return;
                            }

                            if (!analyzeGrammar_derives (tree_kids[kidBase + k2], emptyTP)) 
                                break;
                        }
                    }
                }
            }
        }
    }
}

void analyzeGrammar_checkEmbeddedCombinatorialAmbiguity (const treePT defineTP, const treePT grammarTP)
{
    // We have a recursive combinatorial ambiguity if a repeat can derive another repeat
    if (((tree_trees[defineTP].kind == treeKind_generaterepeat) || (tree_trees[defineTP].kind == treeKind_generatelist) 
                || (tree_trees[defineTP].kind == treeKind_repeat) || (tree_trees[defineTP].kind == treeKind_list))
            && analyzeGrammar_contains (grammarTP, defineTP)) {

        treePT realdefineTP = defineTP;

        if ((tree_trees[defineTP].kind == treeKind_repeat) || (tree_trees[defineTP].kind == treeKind_list)) {
            realdefineTP = tree_kid2TP (defineTP);
        }

        assert ((tree_trees[realdefineTP].kind == treeKind_generaterepeat) || (tree_trees[realdefineTP].kind == treeKind_generatelist));

        const bool islist = tree_trees[realdefineTP].kind == treeKind_generatelist;
        realdefineTP = tree_kid1TP (realdefineTP);

        analyzeGrammar_sortGrammarSymbols (realdefineTP);

        for (int k = 1; k <= analyzeGrammar_nSortedSymbols; k++) {
            treePT symbolTP = analyzeGrammar_sortedSymbols[k];

            if ( ((islist) || ((tree_trees[symbolTP].kind == treeKind_generaterepeat) || (tree_trees[symbolTP].kind == treeKind_repeat))) 
                    && ((!islist) || ((tree_trees[symbolTP].kind == treeKind_generatelist) || (tree_trees[symbolTP].kind == treeKind_list)))) {

                if (analyzeGrammar_derives (realdefineTP, symbolTP)) {
                    string symbolkid1exttype;
                    externalType (*ident_idents[tree_trees[tree_kid1TP (symbolTP)].name], symbolkid1exttype);
                    string defineexttype;
                    externalType (*ident_idents[tree_trees[defineTP].name], defineexttype);
                    string context, message;
                    stringprintf (context, "define '%s'", defineexttype);
                    stringprintf (message, "[%s] is combinatorially ambiguous when parsing sequences of [%s]", defineexttype, symbolkid1exttype);
                    error (context, message, WARNING, 216);
                    string definekid1exttype;
                    externalType (*ident_idents[tree_trees[tree_kid1TP (defineTP)].name], definekid1exttype);
                    string symbolexttype;
                    externalType (*ident_idents[tree_trees[symbolTP].name], symbolexttype);
                    fprintf (stderr, "  since [%s] ->* [%s]\n", definekid1exttype, symbolexttype);  
                    fprintf (stderr, "  (parsing and/or syntax error detection may be slow)\n");
                }
            }
        }

        if (analyzeGrammar_derivesLeading (realdefineTP, defineTP) 
                && (!analyzeGrammar_derives (realdefineTP, defineTP))) {
            string defineexttype;
            externalType (*ident_idents[tree_trees[defineTP].name], defineexttype);
            string definekid1exttype;
            externalType (*ident_idents[tree_trees[tree_kid1TP (defineTP)].name], definekid1exttype);
            string context, message;
            stringprintf (context, "define '%s'", defineexttype);
            stringprintf (message, "[%s] is locally ambiguous when parsing sequences of [%s]", defineexttype, definekid1exttype);
            error (context, message, WARNING, 217);
            string realdefineexttype;
            externalType (*ident_idents[tree_trees[realdefineTP].name], realdefineexttype);
            fprintf (stderr, "  since [%s] ->* [empty]* [%s] ...\n", definekid1exttype, realdefineexttype);
            fprintf (stderr, "  (parsing and/or syntax error detection may be slow)\n");
        }
    }
}

void analyzeGrammar_checkRepeatEmptyAmbiguity (const treePT defineTP, const treePT grammarTP)
{
    // We have a repeat that can derive empty
    if (((tree_trees[defineTP].kind == treeKind_generaterepeat) || (tree_trees[defineTP].kind == treeKind_generatelist) 
                || (tree_trees[defineTP].kind == treeKind_repeat) || (tree_trees[defineTP].kind == treeKind_list))
            && analyzeGrammar_contains (grammarTP, defineTP)) {

        treePT realdefineTP = defineTP;

        if ((tree_trees[defineTP].kind == treeKind_repeat) || (tree_trees[defineTP].kind == treeKind_list)) {
            realdefineTP = tree_kid2TP (defineTP);
        }

        if (analyzeGrammar_derives (tree_kid1TP (realdefineTP), emptyTP)) {
            string defineexttype;
            externalType (*ident_idents[tree_trees[defineTP].name], defineexttype);
            string context, message;
            stringprintf (context, "define '%s'", defineexttype);
            string definekid1exttype;
            externalType (*ident_idents[tree_trees[tree_kid1TP (defineTP)].name], definekid1exttype);
            stringprintf (message, "[%s] is locally ambiguous when parsing sequences of [%s]", defineexttype, definekid1exttype);
            error (context, message, WARNING, 220);
            fprintf (stderr, "  since [%s] ->* [empty]\n", definekid1exttype);
            fprintf (stderr, "  (parsing and/or syntax error detection may be slow)\n");
        }
    }
}

void analyzeGrammar_checkHiddenLeftRecursionAmbiguity (const treePT defineTP, const treePT grammarTP)
{
    // We have a nonterminal that can directly recur on the left
    bool hiddenRecursion = false;

    // Don't check leaves and internal types
    if (((tree_trees[defineTP].kind >= firstLeafKind) && (tree_trees[defineTP].kind != treeKind_literal)) 
            || (stringncmp (*ident_idents[tree_trees[defineTP].name], "__", 2) == 0)) {
        return;
    }

    if ((tree_trees[defineTP].kind == treeKind_generaterepeat) || (tree_trees[defineTP].kind == treeKind_generatelist) 
            || (tree_trees[defineTP].kind == treeKind_repeat) || (tree_trees[defineTP].kind == treeKind_list) 
            || (tree_trees[defineTP].kind == treeKind_push) || (tree_trees[defineTP].kind == treeKind_pop)) {
        // For repeats, no need to check because repeat problems checked separately
        return;
    } else if (tree_trees[defineTP].kind == treeKind_lookahead) {
        // For lookaheads, the lookahead could go on forever if it leads with this type
        hiddenRecursion = analyzeGrammar_derivesLeading (tree_kid1TP (defineTP), defineTP);
    } else if (tree_trees[defineTP].kind == treeKind_leftchoose) {
        // For leftchooses, the only problem is the first choice
        hiddenRecursion = analyzeGrammar_derivesLeading (tree_kid1TP (defineTP), defineTP);
    } else if (tree_trees[defineTP].kind == treeKind_choose) {
        // For chooses, we have a problem if any choice leads with this type
        for (int i = 1; i <= tree_trees[defineTP].count; i++) {
            hiddenRecursion = analyzeGrammar_derivesLeading (tree_kidTP (i, defineTP), defineTP);
            if (hiddenRecursion) break;
        }
    } else if (tree_trees[defineTP].kind == treeKind_order) {
        // For orders, we have a problem if the first child leads with it, 
        // or a child that leads with it follows empty possibilities
        for (int i = 1; i <= tree_trees[defineTP].count; i++) {
            hiddenRecursion = analyzeGrammar_derivesLeading (tree_kidTP (i, defineTP), defineTP);
            if (hiddenRecursion || (!analyzeGrammar_derives (tree_kidTP (i, defineTP), emptyTP))) 
                break;
        }
    } else {
        return;
    }

    // Warn if we find one
    if (hiddenRecursion) {
        string defineexttype;
        externalType (*ident_idents[tree_trees[defineTP].name], defineexttype);
        string context, message;
        stringprintf (context, "define '%s'", defineexttype);
        stringprintf (message, "[%s] is deeply left recursive", defineexttype); 
        error (context, message, WARNING, 221);
        fprintf (stderr, "  (parsing and/or syntax error detection may be slow)\n");
    }
}

void analyzeGrammar_initialize (void) {
    // Precompute empty potential for each type
    for (int i = 1; i <= symbol_nSymbols; i++) {
        tree_setDerivesEmpty (symbol_symbols[i], derivesT_dontknow);
    }

    for (int i = 1; i <= symbol_nSymbols; i++) {
        if (analyzeGrammar_boundedDerivesEmpty (symbol_symbols[i], 0)) {
            tree_setDerivesEmpty (symbol_symbols[i], derivesT_yes);
        } else {
            tree_setDerivesEmpty (symbol_symbols[i], derivesT_no);
        }
    }
}

// Initialization
void analyzeGrammar (void) {
    // 1-origin [1 .. maxSymbols]
    arrayalloc (maxSymbols + 1, treePT, analyzeGrammar_derivesList);
    analyzeGrammar_derivesList[0] = UNUSED;
    arrayalloc (maxSymbols + 1, treePT, analyzeGrammar_derivesLeadingList);
    analyzeGrammar_derivesLeadingList[0] = UNUSED;

    analyzeGrammar_derivesLength = 0;
    analyzeGrammar_derivesThroughRepeat = 0;
    analyzeGrammar_derivesLeadingLength = 0;

    arrayalloc (maxSymbols + 1, treePT, analyzeGrammar_sortedSymbols);
    analyzeGrammar_sortedSymbols[0] = UNUSED;
    arrayalloc (maxSymbols + 1, int, analyzeGrammar_sortedSymbolDepth);
    analyzeGrammar_sortedSymbolDepth[0] = UNUSED;

    analyzeGrammar_nSortedSymbols = 0;
}

